package com.LeetCode.Array;

import org.junit.Test;

import java.io.Serializable;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 线段树
 */
public class TreeArray {
    /**
     * 线段树节点
     */
    private class LineTreeNode{
        int l, r;
        int value;

        LineTreeNode left;
        LineTreeNode right;

    }

    public LineTreeNode root;

    /**
     * 对一个数组构建一棵线段树
     */
    public LineTreeNode buildTree(int[] arr, int l, int r){
        if(l == r){
            LineTreeNode node = new LineTreeNode();
            node.l = l;
            node.r = r;
            node.value = arr[l];
            return node;
        }

        int mid = (l+r) >>> 1;

        LineTreeNode node = new LineTreeNode();
        node.l = l;
        node.r = r;
        node.left = buildTree(arr, l , mid);
        node.right = buildTree(arr, mid + 1, r);
        node.value = node.left.value + node.right.value;


        return node;
    }

    /**
     * 从某个节点开始查询区间和
     */
    public int SearchLine(int l, int r, LineTreeNode cur){
        if(l > r)
            return 0;
        if(cur.l == l && cur.r == r){
            return cur.value;
        }

        int mid = (cur.l + cur.r) >>> 1;

        int res = 0; // 作为最终结果返回

        if(r <= mid)
            res = SearchLine(l , r, cur.left);
        else  if( l > mid)
            res = SearchLine(l , r, cur.right);
        else
            res = SearchLine(l , mid , cur.left) + SearchLine(mid + 1 , r, cur.right);

        return res;
    }

    /**
     * 将下标为 index 的节点的值更新为 val，并更新整棵线段树
     *
     */
    public void update(LineTreeNode cur ,int index, int val){
        if(cur == null)
            return;

        if(cur.l == cur.r && cur.l == index){
            cur.value = val;
            return;
        }

        int mid = (cur.l + cur.r) >>> 1;

        if(index <= mid)
            update(cur.left, index, val);
        else
            update(cur.right, index, val);

        cur.value = cur.left.value + cur.right.value;
    }





    /**
     * 层次遍历
     */
    private void outTree(LineTreeNode root){
        if(root == null)
            return;
        Queue<LineTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            for(int i = 0; i<len; i++){
                LineTreeNode cur = queue.poll();
                System.out.print("[ " + cur.l + " " + cur.r +"  value : " + cur.value +  " ]");
                if(cur.left != null) queue.offer(cur.left);
                if(cur.right != null) queue.offer(cur.right);
            }
            System.out.println();
        }
    }

    @Test
    public void test(){
        int[] arr = {1,3,5,7,9,11};
        root = buildTree(arr, 0 , arr.length-1);
        outTree(root);
        update(root, 1, 5);
        outTree(root);
    }

}


























